package org.example.myleet.p930;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class Solution {

    public int numSubarraysWithSum(int[] nums, int goal) {
        //前缀和
        int[] preSum = new int[nums.length + 1];
        preSum[0] = 0;
        for (int i = 0; i < nums.length; ++i) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        if (preSum[nums.length] < goal) {
            return 0;
        }
        //哈希表记录某个前缀和的出现频率
        Map<Integer, Integer> sumFreqMap = new HashMap<>();
        for (int ps : preSum) {
            int freq = sumFreqMap.getOrDefault(ps, 0);
            ++freq;
            sumFreqMap.put(ps, freq);
        }
        Set<Integer> sumSet = sumFreqMap.keySet();
        int count = 0;
        for (Integer sum : sumSet) {
            if (sum < goal) {
                continue;
            }
            int relSum = sum - goal;
            Integer relSumFreq = sumFreqMap.get(relSum);
            int sumFreq = sumFreqMap.get(sum);
            int ways;
            if (sum == relSum) {
                ways = sumFreq * (sumFreq - 1) / 2;
            } else {
                ways = relSumFreq == null ? 0 : relSumFreq * sumFreq;
            }
            count += ways;
        }
        return count;
    }

//    /**
//     * 通过全部滑窗遍历的方式，超时
//     */
//    public int numSubarraysWithSum(int[] nums, int goal) {
//        int[] preSum = new int[nums.length + 1];
//        preSum[0] = 0;
//        for (int i = 0; i < nums.length; ++i) {
//            preSum[i + 1] = preSum[i] + nums[i];
//        }
//        if (preSum[nums.length] < goal) {
//            return 0;
//        }
//        int count = 0;
//        int winLen = goal > 0 ? goal : 1;
//        for (; winLen <= nums.length; ++winLen) {
//            for (int i = 0; i <= nums.length - winLen; ++i) {
//                int start = i;
//                int end = i + winLen;
//                int winSum = preSum[end] - preSum[start];
//                if (winSum == goal) {
//                    ++count;
//                }
//            }
//        }
//        return count;
//    }
}
